package 数据结构与算法.实验三;

import java.util.LinkedList;
import java.util.Queue;

public class QueueMaze {
    public static void main(String[] args) {
        int [][] maze = {
                {1, 1, 1, 1, 1, 1},
                {1, 0, 1, 0, 0, 1},
                {1, 0, 0, 1, 1, 1},
                {1, 0, 1, 0, 0, 1},
                {1, 0, 0, 0, 0, 1},
                {1, 1, 1, 1, 1, 1}

        };
        QueueNode.Maze_End(maze, 1, 1, 4, 4);
    }

}
class QueueNode{
    int x;
    int y;
    QueueNode previous;

    public QueueNode(int x, int y){
        this.x = x;
        this.y = y;
        this.previous = null;
    }
    public static boolean Maze_End(int[][] maze, int startX, int startY, int endX, int endY) {
        Queue<QueueNode> queue = new LinkedList<>();
        QueueNode startNode = new QueueNode(startX, startY);
        queue.offer(startNode);
        maze[startY][startX] = -1;
        QueueNode popNode = null;
        while (!queue.isEmpty()) {
            popNode = queue.poll();
            if (popNode.x == endX && popNode.y == endY) {
                showByEndNode(popNode);
                return true;
            }
            for (int i = 0; i < 4; i++) {
                int insertX = 0;
                int insertY = 0;
                //四个方向的X和Y
                switch (i) {
                    case 0:
                        insertX = popNode.x - 1;
                        insertY = popNode.y;
                        break;
                    case 1:
                        insertX = popNode.x + 1;
                        insertY = popNode.y;
                        break;
                    case 2:
                        insertX = popNode.x;
                        insertY = popNode.y + 1;
                        break;
                    case 3:
                        insertX = popNode.x;
                        insertY = popNode.y - 1;
                        break;
                }

                if (insertX >= 0 && insertX < maze.length && insertY >= 0 && insertY < maze.length
                        && maze[insertY][insertX] == 0) {
                    maze[insertY][insertX] = -1;
                    QueueNode node = new QueueNode(insertX, insertY);
                    node.previous = popNode;
                    queue.offer(node);
                }
            }
        }
        return false;
    }

    public static void showByEndNode(QueueNode endNode) {
        while (endNode != null) {
            System.out.printf("[%d,%d] ", endNode.y, endNode.x);
            endNode = endNode.previous;
        }
    }
}
